{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Construct Product Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: constructProductMatrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #构造乘积矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始、大小为 <code>n * m</code> 的二维整数矩阵 <code><font face=\"monospace\">grid</font></code><font face=\"monospace\"> ，定义一个下标从 <strong>0</strong> 开始、大小为 <code>n * m</code> 的的二维矩阵</font> <code>p</code>。如果满足以下条件，则称 <code>p</code> 为 <code>grid</code> 的 <strong>乘积矩阵</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>对于每个元素 <code>p[i][j]</code> ，它的值等于除了 <code>grid[i][j]</code> 外所有元素的乘积。乘积对 <code>12345</code> 取余数。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回 <code>grid</code> 的乘积矩阵。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,2],[3,4]]\n",
    "<strong>输出：</strong>[[24,12],[8,6]]\n",
    "<strong>解释：</strong>p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24\n",
    "p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12\n",
    "p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8\n",
    "p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6\n",
    "所以答案是 [[24,12],[8,6]] 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[12345],[2],[1]]\n",
    "<strong>输出：</strong>[[2],[0],[0]]\n",
    "<strong>解释：</strong>p[0][0] = grid[0][1] * grid[0][2] = 2 * 1 = 2\n",
    "p[0][1] = grid[0][0] * grid[0][2] = 12345 * 1 = 12345. 12345 % 12345 = 0 ，所以 p[0][1] = 0\n",
    "p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0 ，所以 p[0][2] = 0\n",
    "所以答案是 [[2],[0],[0]] 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n == grid.length&nbsp;&lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= m == grid[i].length&nbsp;&lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>2 &lt;= n * m &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= grid[i][j] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [construct-product-matrix](https://leetcode.cn/problems/construct-product-matrix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [construct-product-matrix](https://leetcode.cn/problems/construct-product-matrix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[3,4]]', '[[12345],[2],[1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        prod = 1\n",
    "        M = 12345\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        \n",
    "        prefix = [1]\n",
    "        for i, j in product(range(m), range(n)):\n",
    "            prod = (prefix[-1] * grid[i][j]) % M\n",
    "            prefix.append(prod)\n",
    "\n",
    "        suffix = [1]\n",
    "        for i, j in product(reversed(range(m)), reversed(range(n))):\n",
    "            prod = (suffix[-1] * grid[i][j]) % M\n",
    "            suffix.append(prod)\n",
    "\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i, j in product(range(m), range(n)):\n",
    "            idx = i * n + j\n",
    "            ans[i][j] = (prefix[idx] * suffix[m*n-1-idx]) % M\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        \n",
    "        s = [i for j in grid for i in j][::-1]\n",
    "        f = [1] * (m*n)\n",
    "        res = 1\n",
    "        for i,x in enumerate(s):\n",
    "            f[i] = res % 12345\n",
    "            res = (res*x) % 12345\n",
    "        f = f[::-1]\n",
    "        # print(s, f)\n",
    "        t = 1\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                temp = grid[i][j]\n",
    "                grid[i][j] = (f[i*m+j] * t) % 12345\n",
    "                t = (t * temp) % 12345\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIV = 12345\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\tdef mul(self, a, b):\n",
    "\t\treturn a * (b % DIV) % DIV\n",
    "\n",
    "\tdef constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "\t\tn = len(grid)\n",
    "\t\tm = len(grid[0])\n",
    "\t\tflat = []\n",
    "\t\tfor i in grid:\n",
    "\t\t\tflat.extend(i)\n",
    "\n",
    "\t\tret = grid.copy()\n",
    "\t\t# 顺序遍历\n",
    "\t\tseq = [1]\n",
    "\t\tprod = 1\n",
    "\t\tfor i in range(len(flat) - 1):\n",
    "\t\t\tprod = self.mul(prod, flat[i])\n",
    "\t\t\tseq.append(prod)\n",
    "\t\t# 逆序遍历\n",
    "\t\trev = [1]\n",
    "\t\tprod = 1\n",
    "\t\tfor i in range(len(flat) - 1, 0, -1):\n",
    "\t\t\tprod = self.mul(prod, flat[i])\n",
    "\t\t\trev.append(prod)\n",
    "\t\tind = 0\n",
    "\t\tind_rev = -1\n",
    "\t\tfor i in range(n):\n",
    "\t\t\tfor j in range(m):\n",
    "\t\t\t\tret[i][j] = self.mul(seq[ind], rev[ind_rev])\n",
    "\t\t\t\tind += 1\n",
    "\t\t\t\tind_rev -= 1\n",
    "\t\treturn ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from collections import defaultdict, deque\n",
    "from sortedcontainers import SortedList\n",
    "from functools import lru_cache\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(999999)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param grid:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        tt = 1\n",
    "        cnt1 = 0\n",
    "        m1 = {}\n",
    "        has = False\n",
    "        cntx = 0\n",
    "        for k, v in enumerate(grid):\n",
    "            for k2, v2 in enumerate(v):\n",
    "                if v2 % 12345 == 0:\n",
    "\n",
    "                    has = True\n",
    "                    rm = v2 // 12345\n",
    "                    cnt1 += rm\n",
    "                    m1[(k,k2)] = rm\n",
    "                    cntx += 1\n",
    "                else:\n",
    "                    tt *= v2\n",
    "\n",
    "        for k, v in enumerate(grid):\n",
    "            for k2, v2 in enumerate(v):\n",
    "                if (k,k2) in m1:\n",
    "                    if cntx == 1:\n",
    "                        grid[k][k2] = ((cnt1-m1[(k,k2)]) +  tt) % 12345\n",
    "                    else:\n",
    "                        grid[k][k2] = 0\n",
    "                else:\n",
    "                    if has:\n",
    "                        grid[k][k2] = 0\n",
    "                    else:\n",
    "                        grid[k][k2] = tt // v2  % 12345\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        MOD = 12345\n",
    "        g = [grid[i][j] % MOD for i in range(m) for j in range(n)]\n",
    "        # print(g)\n",
    "        left, right = [1] * (m * n), [1] * (m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                left[i * n + j] = 1 if not i and not j else (left[i * n + j - 1] * g[i * n + j - 1]) % MOD\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                right[i * n + j] = 1 if i == m - 1 and j == n - 1 else (right[i * n + j + 1] * g[i * n + j + 1]) % MOD\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                grid[i][j] = left[i * n + j] * right[i * n + j] % MOD\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        MOD = 12345\n",
    "        mul = 1\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        cnt = 0\n",
    "        \n",
    "        flag = False\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] % MOD == 0:\n",
    "                    cnt += 1\n",
    "                if cnt == 2:\n",
    "                    flag = True\n",
    "                    break\n",
    "                mul *= grid[i][j]\n",
    "            if flag == True:\n",
    "                break\n",
    "        if flag == True:\n",
    "            return [[0] * m] * n\n",
    "        \n",
    "        res = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                res[i][j] = (mul // grid[i][j]) % MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        MOD = 12345\n",
    "        mul = 1\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        cnt = 0\n",
    "        \n",
    "        flag = False\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] % MOD == 0:\n",
    "                    cnt += 1\n",
    "                if cnt == 2:\n",
    "                    flag = True\n",
    "                    break\n",
    "                mul *= grid[i][j]\n",
    "            if flag == True:\n",
    "                break\n",
    "        if flag == True:\n",
    "            return [[0] * m] * n\n",
    "        \n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            tmp = []\n",
    "            for j in range(m):\n",
    "                tmp.append((mul // grid[i][j]) % MOD)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        # 前后缀分解\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        p = [[0] * m for _ in range(n)]\n",
    "        suffix = 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(m - 1, -1, -1):\n",
    "                p[i][j] = suffix\n",
    "                suffix = suffix * grid[i][j] % 12345\n",
    "        prefix = 1\n",
    "        for i, line in enumerate(grid):\n",
    "            for j, x in enumerate(line):\n",
    "                p[i][j] = p[i][j] * prefix % 12345\n",
    "                prefix = prefix * x % 12345\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        count12345 = 0\n",
    "        accumulated = 1\n",
    "        for line in grid:\n",
    "            for x in line:\n",
    "                if x % 12345 == 0:\n",
    "                    count12345 += 1\n",
    "                    if count12345 > 1:\n",
    "                        return [[0] * m for _ in range(n)]\n",
    "                else:\n",
    "                    accumulated = accumulated * x\n",
    "        for i, line in enumerate(grid):\n",
    "            for j, x in enumerate(line):\n",
    "                if count12345 == 0:\n",
    "                    grid[i][j] = (accumulated // x) % 12345\n",
    "                elif x % 12345 == 0:\n",
    "                    grid[i][j] = accumulated % 12345\n",
    "                else:\n",
    "                    grid[i][j] = 0\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        prefix=[1]\n",
    "        row=len(grid)\n",
    "        col=len(grid[0])\n",
    "        for r in range(row):\n",
    "            for c in range(col):\n",
    "                prefix.append(prefix[-1]*grid[r][c]%12345)\n",
    "        n=row*col\n",
    "        suffix=[1]\n",
    "        for r in range(row-1,-1,-1):\n",
    "            for c in range(col-1,-1,-1):\n",
    "                suffix.append(suffix[-1]*grid[r][c]%12345)\n",
    "        suffix=suffix[::-1]\n",
    "        ans=[[0]*col for _ in range(row)]\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                cur=i*col+j\n",
    "                ans[i][j]=prefix[cur]*suffix[cur+1]%12345\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        mod = 12345\n",
    "        cur = 1 \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res[i][j] = cur \n",
    "                cur *= grid[i][j]\n",
    "                cur %= mod \n",
    "                \n",
    "        cur = 1\n",
    "        for i in range(m - 1, - 1, - 1):\n",
    "            for j in range(n - 1, - 1, - 1):\n",
    "                res[i][j] = res[i][j] * cur % mod \n",
    "                cur *= grid[i][j]\n",
    "                cur %= mod \n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        # 左上，右下，蛇型模拟\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        ans = [[1 for i in range(m)] for j in range(n)]\n",
    "        mn = m * n\n",
    "        left = [1 for i in range(mn)]\n",
    "        right = [1 for i in range(mn)]\n",
    "        MOD = 12345\n",
    "        temp = 1\n",
    "        pos = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                temp = (temp * grid[i][j]) % MOD\n",
    "                left[pos] = temp\n",
    "                pos = pos + 1\n",
    "        temp = 1\n",
    "        pos = m * n - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(m - 1, -1, -1):\n",
    "                temp = (temp * grid[i][j]) % MOD\n",
    "                right[pos] = temp\n",
    "                pos = pos - 1\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                pos = i * m + j\n",
    "                if pos == 0:\n",
    "                    ans[i][j] = right[1]\n",
    "                elif pos == m * n - 1:\n",
    "                    ans[i][j] = left[-2]\n",
    "                else:\n",
    "                    ans[i][j] = (left[pos - 1] * right[pos + 1]) % MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"Created: 2023/10/15\"\"\"\n",
    "from typing import List, Dict\n",
    "\n",
    "Mod = 12345\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        big_table = []\n",
    "        table = [1] * (m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                big_table.append(grid[i][j])\n",
    "\n",
    "        def f(i, j):\n",
    "            if i == j:\n",
    "                return big_table[i] % Mod\n",
    "            mid = (i+j) // 2\n",
    "            left = f(i, mid)\n",
    "            right = f(mid+1, j)\n",
    "            for i in range(i, mid+1):\n",
    "                table[i] = table[i] * right % Mod\n",
    "            for i in range(mid+1, j+1):\n",
    "                table[i] = table[i] * left % Mod\n",
    "            return left * right % Mod\n",
    "        f(0, m*n-1)\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            tmp = []\n",
    "            for j in range(n):\n",
    "                tmp.append(table[i*n+j])\n",
    "            ans.append(tmp)\n",
    "        return ans\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    s = Solution()\n",
    "    s.constructProductMatrix([[1,2],[3,4]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 12345\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        ans = [[1] * m for _ in range(n)]\n",
    "        tot = [1] * n\n",
    "        for i in range(n):\n",
    "            pref = [1] * (m + 1)\n",
    "            suff = [1] * (m + 1)\n",
    "            res = 1\n",
    "            for j in range(m):\n",
    "                res *= grid[i][j]\n",
    "                res %= mod\n",
    "                pref[j+1] = pref[j] * grid[i][j] % mod\n",
    "            for j in range(m-1, -1, -1):\n",
    "                suff[j] = suff[j+1] * grid[i][j] % mod\n",
    "            for j in range(m):\n",
    "                ans[i][j] = pref[j] * suff[j+1] % mod\n",
    "            tot[i] = res\n",
    "        pref = [1] * (n + 1)\n",
    "        suff = [1] * (n + 1)\n",
    "        for j in range(n):\n",
    "            pref[j+1] = pref[j] * tot[j] % mod\n",
    "        for j in range(n-1, -1, -1):\n",
    "            suff[j] = suff[j+1] * tot[j] % mod\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ans[i][j] *= pref[i] * suff[i+1]\n",
    "                ans[i][j] %= mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n,m=len(grid),len(grid[0])\n",
    "        snt1,snt2,snt3,mul=0,0,0,1\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                cnt1,cnt2,cnt3=0,0,0\n",
    "                while(grid[i][j]%3==0):grid[i][j]//=3;cnt1+=1\n",
    "                while(grid[i][j]%5==0):grid[i][j]//=5;cnt2+=1\n",
    "                while(grid[i][j]%823==0):grid[i][j]//=823;cnt3+=1\n",
    "                snt1,snt2,snt3=snt1+cnt1,snt2+cnt2,snt3+cnt3\n",
    "                mul=mul*grid[i][j]%12345\n",
    "                grid[i][j]=[cnt1,cnt2,cnt3,grid[i][j]]\n",
    "        print(grid)\n",
    "        def ksm(u,v):\n",
    "            res=1\n",
    "            while(v):\n",
    "                if(v&1):res=res*u%12345\n",
    "                u=u*u%12345;v>>=1\n",
    "            return res\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if(snt1-grid[i][j][0]>0 and snt2-grid[i][j][1]>0 and snt3-grid[i][j][2]>0):grid[i][j]=0\n",
    "                else:grid[i][j]=mul*ksm(grid[i][j][3],6575)*ksm(3,snt1-grid[i][j][0])*ksm(5,snt2-grid[i][j][1])*ksm(823,snt3-grid[i][j][2])%12345\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mod = 12345\n",
    "        l = m * n\n",
    "        grid1 = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                grid1.append(grid[i][j] % mod)\n",
    "        grid = grid1\n",
    "        pre = [1]\n",
    "        tail = [1]\n",
    "        for i in range(l):\n",
    "            pre.append(pre[-1] * grid[i] % mod)\n",
    "            i = l - i - 1\n",
    "            tail.append(tail[-1] * grid[i] % mod)\n",
    "        tail = tail[::-1]\n",
    "        res = [[1 for i in range(n)] for j in range(m)]\n",
    "        for i in range(l):\n",
    "            res[i // n][i % n] = pre[i] * tail[i + 1] % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, a: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(a), len(a[0])\n",
    "        g = m * n\n",
    "        d = [0] * (4 * g + 1)\n",
    "        mod = 12345\n",
    "        def build(s, t, p):\n",
    "            # 对 [s,t] 区间建立线段树,当前根的编号为 p\n",
    "            if s == t:\n",
    "                tt = s - 1\n",
    "                d[p] = a[tt // n][tt % n]\n",
    "                return\n",
    "            mid = s + ((t - s) >> 1)\n",
    "            # 移位运算符的优先级小于加减法，所以加上括号\n",
    "            # 如果写成 (s + t) >> 1 可能会超出 int 范围\n",
    "            build(s, mid, p * 2); build(mid + 1, t, p * 2 + 1)\n",
    "            # 递归对左右区间建树\n",
    "            d[p] = d[p * 2] * d[(p * 2) + 1] % mod\n",
    "\n",
    "        def getmul(l, r, s, t, p):\n",
    "            if l > r: return 1\n",
    "            #print(1)\n",
    "            # [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号\n",
    "            if l <= s and t <= r:\n",
    "                return d[p] # 当前区间为询问区间的子集时直接返回当前区间的和\n",
    "            mid = s + ((t - s) >> 1); mul = 1\n",
    "            if l <= mid:\n",
    "                mul = mul * getmul(l, r, s, mid, p * 2) % mod\n",
    "            # 如果左儿子代表的区间 [s, m] 与询问区间有交集, 则递归查询左儿子\n",
    "            if r > mid:\n",
    "                mul = mul * getmul(l, r, mid + 1, t, p * 2 + 1) % mod\n",
    "            # 如果右儿子代表的区间 [m + 1, t] 与询问区间有交集, 则递归查询右儿子\n",
    "            return mul\n",
    "        build(1, g, 1)\n",
    "        #print(d)\n",
    "        res = [[1] * n for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                kk = i * n + j + 1\n",
    "                res[i][j] = getmul(1, kk - 1, 1, g, 1) * getmul(kk + 1, g, 1, g, 1) % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        mod = 12345\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        suf = [[1] * n for _ in range(m)]\n",
    "        cur = 1\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                suf[i][j] = cur\n",
    "                cur = cur * grid[i][j] % mod\n",
    "        pres = 1\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res[i][j] = pres * suf[i][j] % mod\n",
    "                pres = pres * grid[i][j] % mod\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, g: List[List[int]]) -> List[List[int]]:\n",
    "        s = 1\n",
    "        mod = 12345\n",
    "        n, m = len(g), len(g[0])\n",
    "        suf = [[1] * (m) for _ in range(n)]\n",
    "        x = 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(m - 1, -1, -1):\n",
    "                suf[i][j] = x\n",
    "                x *= g[i][j] \n",
    "                x %= mod\n",
    "                \n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            t = []\n",
    "            for j in range(m):\n",
    "                t.append(s * suf[i][j] % mod)\n",
    "                s *= g[i][j]\n",
    "                s %= mod\n",
    "            res.append(t)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        max_pro = 1\n",
    "        glen = len(grid)\n",
    "        if glen > 0:\n",
    "            gglen = len(grid[0])\n",
    "        pre = [[1 for i in range(gglen)] for j in range(glen)]\n",
    "\n",
    "        for i in range(glen):\n",
    "            for j in range(gglen):\n",
    "                pre[i][j] = max_pro\n",
    "                max_pro=grid[i][j]*max_pro%12345 \n",
    "        #print(pre)\n",
    "        pos = [[1 for i in range(gglen)] for j in range(glen)]\n",
    "        max_pro = 1\n",
    "        for i in range(glen-1,-1,-1):\n",
    "            for j in range(gglen-1,-1,-1):\n",
    "                pre[i][j] = max_pro * pre[i][j] % 12345 \n",
    "                max_pro=max_pro*grid[i][j]\n",
    "\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        right = [[1] * n for _ in  range(m)]\n",
    "        temp = 1\n",
    "        for i, j in product(reversed(range(m)), reversed(range(n))):\n",
    "            right[i][j] = temp \n",
    "            temp = (temp * grid[i][j]) % 12345 \n",
    "        left = 1\n",
    "        res = [[0] * n for _ in  range(m)]\n",
    "        for i, j in product(range(m), range(n)):\n",
    "            res[i][j] = (right[i][j] * left) % 12345\n",
    "            left = (left * grid[i][j]) % 12345\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        mod = 12345\n",
    "\n",
    "        ls = [[grid[r][c] for c in range(n)] for r in range(m)]\n",
    "        rs = [[grid[r][c] for c in range(n)] for r in range(m)]\n",
    "        us = [-1]*m\n",
    "        ds = [-1]*m\n",
    "        \n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                ls[r][c]=ls[r][c-1]*grid[r][c]%mod if c else grid[r][c]\n",
    "            for c in range(n-1,-1,-1):\n",
    "                rs[r][c]=rs[r][c+1]*grid[r][c]%mod if c<n-1 else grid[r][c]        \n",
    "\n",
    "        for r in range(m):\n",
    "            us[r]=us[r-1]*ls[r][-1]%mod if r else ls[r][-1]\n",
    "        for r in range(m-1,-1,-1):\n",
    "            ds[r]=ds[r+1]*ls[r][-1]%mod if r<m-1 else ls[r][-1]\n",
    "                    \n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                u = us[r-1] if r else 1\n",
    "                d = ds[r+1] if r<m-1 else 1\n",
    "                l = ls[r][c-1] if c else 1\n",
    "                rr = rs[r][c+1] if c<n-1 else 1\n",
    "                grid[r][c]=u*d*l*rr%mod\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        mod=12345\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "        t=n*m\n",
    "        ans=[[0]*m for _ in range(n)]\n",
    "        pre=[0]*t\n",
    "        suf=[0]*t\n",
    "        \n",
    "        @cache\n",
    "        def get(i):\n",
    "            return grid[i//m][i%m]\n",
    "        def set(i,v):\n",
    "            grid[i//m][i%m]=v\n",
    "        pre[0]=get(0)%mod\n",
    "        for i in range(1,t):\n",
    "            pre[i]=pre[i-1]*get(i)%mod\n",
    "        suf[-1]=get(t-1)%mod\n",
    "        for i in range(t-2,-1,-1):\n",
    "            suf[i]=suf[i+1]*get(i)%mod\n",
    "        set(0,suf[1])\n",
    "        set(t-1,pre[t-2])\n",
    "        for i in range(1,t-1):\n",
    "            set(i,pre[i-1]*suf[i+1]%mod)\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 12345\n",
    "\n",
    "\n",
    "def gcd(a, b):\n",
    "    if a > b:\n",
    "        a, b = b, a\n",
    "\n",
    "    while a:\n",
    "        a, b = b % a, a\n",
    "    return b\n",
    "\n",
    "\n",
    "def get_prime(N):\n",
    "    prime_vals = []\n",
    "    flag = [True] * (N + 1)\n",
    "    for val in range(2, N + 1):\n",
    "        if flag[val]:\n",
    "            prime_vals.append(val)\n",
    "\n",
    "        for p_val in prime_vals:\n",
    "            if val * p_val > N:\n",
    "                break\n",
    "\n",
    "            flag[val * p_val] = False\n",
    "\n",
    "            if val % p_val == 0:\n",
    "                break\n",
    "\n",
    "    return prime_vals\n",
    "\n",
    "\n",
    "primes = get_prime(34000)  # 注意这里的100000需要大于等于 sqrt(最大的需要分解质因数的数值)\n",
    "\n",
    "\n",
    "# 分解质因数函数，返回元组数组[ (质因子1, 次幂1)， (质因子2, 次幂2)， (质因子3, 次幂3) ...... ]\n",
    "# 质因子的数值升序排列\n",
    "def devide_prime(val):\n",
    "    ans = {}\n",
    "\n",
    "\n",
    "    for i in primes:\n",
    "        if i * i > val:\n",
    "            break\n",
    "\n",
    "        if val % i == 0:\n",
    "            cnt = 0\n",
    "            while val % i == 0:\n",
    "                val //= i\n",
    "                cnt += 1\n",
    "\n",
    "            ans[i] = cnt\n",
    "\n",
    "        if val == 1:\n",
    "            break\n",
    "\n",
    "    # 特判最后可能剩下的大于sqrt(val)的最大的质因子\n",
    "    if val != 1:\n",
    "        ans[val] = 1\n",
    "\n",
    "    return ans\n",
    "\n",
    "def pow_mod(a, k, p):\n",
    "    ans = 1\n",
    "    pow_val = a % p  # a的2^0次方，数值就是a\n",
    "    while k != 0:\n",
    "        if k & 1 != 0:\n",
    "            ans = (ans * pow_val) % p\n",
    "        pow_val = (pow_val ** 2) % p\n",
    "        k >>= 1\n",
    "    return ans\n",
    "\n",
    "\n",
    "# 求a, b最大公约数，同时求出裴蜀定理中的一组系数x, y， 满足x*a + y*b = gcd(a, b)\n",
    "def exp_gcd(a, b):\n",
    "    flag = True\n",
    "    if a > b:\n",
    "        flag = False\n",
    "        a, b = b, a\n",
    "\n",
    "    if a == 0:\n",
    "        return (b, 0, 1) if flag else (b, 1, 0)\n",
    "\n",
    "    gcd_val, x, y = exp_gcd(b % a, a)\n",
    "    new_x = y - x * (b // a)\n",
    "    new_y = x\n",
    "    return (gcd_val, new_x, new_y) if flag else (gcd_val, new_y, new_x)\n",
    "\n",
    "\n",
    "# 求val对mod取模的逆元, 也就是求出的ans满足(val * ans) 和 1 对 mod 求模同余\n",
    "def get_mul_mod_rev_meta(val, mod):\n",
    "    gcd_val, x, _ = exp_gcd(val, mod)\n",
    "    return None if gcd_val != 1 else x\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        c = Counter()\n",
    "        mm = {}\n",
    "\n",
    "        c1, c2, c3 = 0, 0, 0\n",
    "        for ll in grid:\n",
    "            for v in ll:\n",
    "                c[v] += 1\n",
    "\n",
    "                if v != 1:\n",
    "                    div = devide_prime(v)\n",
    "                    for p, cnt in div.items():\n",
    "                        if p == 3:\n",
    "                            c1 += 1\n",
    "                        if p == 5:\n",
    "                            c2 += 1\n",
    "                        if p == 823:\n",
    "                            c3 += 1\n",
    "\n",
    "                        if p not in mm:\n",
    "                            mm[p] = 0\n",
    "                        mm[p] += cnt\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if c1 >= 2 and c2 >= 2 and c3 >= 2:\n",
    "            return [[0] * n for i in range(m)]\n",
    "\n",
    "        Tot = 1\n",
    "        for val, cnt in c.items():\n",
    "            Tot *= pow_mod(val, cnt, MOD)\n",
    "            Tot %= MOD\n",
    "\n",
    "        kk = {}\n",
    "        for p, cnt in mm.items():\n",
    "            kk[p] = pow_mod(p, cnt, MOD)\n",
    "\n",
    "        p_arr = list(mm.keys())\n",
    "        N = len(p_arr)\n",
    "        p2idx = {}\n",
    "        for i in range(N):\n",
    "            p2idx[p_arr[i]] = i\n",
    "\n",
    "        vals = [0] * (4 * N + 100)\n",
    "        if N == 0:\n",
    "            return [[1]*n for i in range(m)]\n",
    "\n",
    "        def push_up(x):\n",
    "            vals[x] = vals[x << 1] * vals[(x<<1) + 1]\n",
    "            vals[x] %= MOD\n",
    "\n",
    "        def build(x, l, r):\n",
    "            if l == r:\n",
    "                p = p_arr[l]\n",
    "                vals[x] = kk[p]\n",
    "                return\n",
    "\n",
    "            mid = (l + r) >> 1\n",
    "            build(x<<1, l, mid)\n",
    "            build((x<<1) | 1, mid+1, r)\n",
    "            push_up(x)\n",
    "\n",
    "        def query(x, l, r, ql, qr):\n",
    "            if l == ql and r == qr:\n",
    "                return vals[x]\n",
    "\n",
    "            mid = (l + r) >> 1\n",
    "            if qr <= mid:\n",
    "                return query(x<<1, l, mid, ql, qr)\n",
    "            elif ql >= mid+1:\n",
    "                return query((x<<1)|1, mid+1, r, ql, qr)\n",
    "            else:\n",
    "                val1 = query(x<<1, l, mid, ql, mid)\n",
    "                val2 = query((x<<1)|1, mid+1, r, mid+1, qr)\n",
    "                return (val1 * val2) % MOD\n",
    "\n",
    "        build(1, 0, N-1)\n",
    "\n",
    "\n",
    "        cc = {}\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ret = [[0] * n for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] in cc:\n",
    "                    ret[i][j] = cc[grid[i][j]]\n",
    "                    continue\n",
    "\n",
    "                if grid[i][j] == 1:\n",
    "                    ret[i][j] = Tot\n",
    "                    cc[grid[i][j]] = Tot\n",
    "                    continue\n",
    "\n",
    "                if c1 >= 2 and c2 >= 2 and c3 >= 2:\n",
    "                    ret[i][j] = 0\n",
    "                    cc[grid[i][j]] = 0\n",
    "                    continue\n",
    "\n",
    "                if gcd(grid[i][j], MOD) != 1:\n",
    "                    if c1 == 1 and c2 == 1 and c3 == 1:\n",
    "                        f = False\n",
    "                        if grid[i][j] % 3 == 0:\n",
    "                            f = True\n",
    "                        if grid[i][j] % 5 == 0:\n",
    "                            f = True\n",
    "                        if grid[i][j] % 823 == 0:\n",
    "                            f = True\n",
    "\n",
    "                        if not f:\n",
    "                            ret[i][j] = 0\n",
    "                            cc[grid[i][j]] = 0\n",
    "                            continue\n",
    "\n",
    "                    div = devide_prime(grid[i][j])\n",
    "                    idx_arr = [p2idx[k] for k in div.keys()]\n",
    "                    idx_arr.sort()\n",
    "\n",
    "                    ans = 1\n",
    "                    prev_idx = -1\n",
    "\n",
    "                    for idx in idx_arr:\n",
    "                        a, b = prev_idx+1, idx - 1\n",
    "\n",
    "                        p = p_arr[idx]\n",
    "                        p_cnt = mm[p] - div[p]\n",
    "                        ans *= pow_mod(p, p_cnt, MOD)\n",
    "                        ans %= MOD\n",
    "\n",
    "                        if b >= a:\n",
    "                            ans *= query(1, 0, N-1, a, b)\n",
    "                            ans %= MOD\n",
    "\n",
    "                        prev_idx = idx\n",
    "\n",
    "                    lst_idx = idx_arr[-1]\n",
    "                    if lst_idx + 1 <= N-1:\n",
    "                        ans *= query(1, 0, N-1, lst_idx+1, N-1)\n",
    "                        ans %= MOD\n",
    "\n",
    "\n",
    "                    ret[i][j] = ans\n",
    "                    cc[grid[i][j]] = ans\n",
    "\n",
    "                else:\n",
    "                    rev = get_mul_mod_rev_meta(grid[i][j], MOD)\n",
    "                    ret[i][j] = (Tot * rev) % MOD\n",
    "                    cc[grid[i][j]] = ret[i][j]\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        pre = [[1]*n for _ in range(m)]\n",
    "        suf = [[1]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0 and j==0:\n",
    "                    pre[i][j] = 1\n",
    "                elif j == 0:\n",
    "                    pre[i][j] = pre[i-1][n-1]* grid[i-1][n-1]%12345\n",
    "                else:\n",
    "                    pre[i][j] = pre[i][j-1]* grid[i][j-1]%12345\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if i==m-1 and j==n-1:\n",
    "                    suf[i][j] = 1\n",
    "                elif j==n-1:\n",
    "                    suf[i][j] = suf[i+1][0] * grid[i+1][0]%12345\n",
    "                else:\n",
    "                    suf[i][j] = suf[i][j+1] *grid[i][j+1]%12345\n",
    "        result = [[1]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                result[i][j] = pre[i][j]*suf[i][j]%12345\n",
    "                \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        sumnum = 1\n",
    "        modnum = 12345\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        pre = [[1]*n for _ in range(m)]\n",
    "        after = [[1]*n for _ in range(m)]\n",
    "        ans = [[1]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                print(i,j)\n",
    "                pre[i][j] = sumnum\n",
    "                sumnum = (sumnum * grid[i][j]) % modnum\n",
    "        sumnum = 1\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                after[i][j] = sumnum\n",
    "                sumnum = (sumnum * grid[i][j]) % modnum\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = (pre[i][j] * after[i][j]) % modnum\n",
    "        # print(grid, pre, after, ans)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "    利用前后缀分解分别计算前面与后面的数的乘积\n",
    "    重点: 从左向右 从上向下拉直为一个一维向量\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pre = [[1]*n for _ in range(m)]\n",
    "        mod = 12345\n",
    "        num = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pre[i][j] = num\n",
    "                num = (num * grid[i][j]) % mod\n",
    "\n",
    "        suf = [[1]*n for _ in range(m)]\n",
    "        mod = 12345\n",
    "        num = 1\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                suf[i][j] = num\n",
    "                num = (num * grid[i][j]) % mod\n",
    "        \n",
    "        return [[pre[i][j]*suf[i][j]%mod for j in range(n)] for i in range(m)]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "M = 12345\n",
    "\n",
    "mulmod = np.frompyfunc(lambda a, b: a * b % M ,2 ,1)\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        grid = np.concatenate(([1], np.array(grid).flatten().astype(int), [1]))\n",
    "        prefix = mulmod.accumulate(grid[:-2])\n",
    "        suffix = np.flip(mulmod.accumulate(np.flip(grid[2:])))\n",
    "        return (prefix * suffix % M).reshape((n, -1)).tolist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        sumnum = 1\n",
    "        modnum = 12345\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        pre = [[1]*n for _ in range(m)]\n",
    "        after = [[1]*n for _ in range(m)]\n",
    "        ans = [[1]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                print(i,j)\n",
    "                pre[i][j] = sumnum\n",
    "                sumnum = (sumnum * grid[i][j]) % modnum\n",
    "        sumnum = 1\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                after[i][j] = sumnum\n",
    "                sumnum = (sumnum * grid[i][j]) % modnum\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = (pre[i][j] * after[i][j]) % modnum\n",
    "        print(grid, pre, after, ans)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        pre = [[1 for j in range(m)] for i in range(n)]\n",
    "        post = [[1 for j in range(m)] for i in range(n)]\n",
    "        prod = 1\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                pre[i][j] = prod\n",
    "                prod = prod * grid[i][j] % 12345\n",
    "        prod = 1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(m-1, -1, -1):\n",
    "                post[i][j] = prod\n",
    "                prod = prod * grid[i][j] % 12345\n",
    "        \n",
    "        return [[pre[i][j] * post[i][j] % 12345 for j in range(m)] for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        MOD=12345\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        row=[]\n",
    "        suf_col=[[1] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            mul=1\n",
    "            for j in range(n):\n",
    "                mul=mul*grid[i][j]%MOD\n",
    "                suf_col[i].append(suf_col[i][-1]*grid[i][-1-j]%MOD)\n",
    "            row.append(mul)\n",
    "        pre_m=[1]\n",
    "        for i in range(m):\n",
    "            pre_m.append(pre_m[-1]*row[i]%MOD)\n",
    "        suf_m=[1]\n",
    "        for i in range(m-1,-1,-1):\n",
    "            suf_m.append(suf_m[-1]*row[i]%MOD)\n",
    "        ans=[[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            pre_col=1\n",
    "            for j in range(n):\n",
    "                ans[i][j]=pre_m[i]*suf_m[m-i-1]*pre_col*suf_col[i][n-j-1]%MOD\n",
    "                pre_col=pre_col*grid[i][j]%MOD\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "from itertools import accumulate\n",
    "M = 12345\n",
    "\n",
    "mulmod = lambda a, b: a * b % M\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        grid = np.array(grid).flatten().tolist()\n",
    "        prefix = np.array(list(accumulate(grid[:-1], initial=1, func=mulmod)))\n",
    "        suffix = np.array(list(accumulate(grid[n*m-1:0:-1], initial=1,func=mulmod)))\n",
    "        return np.reshape(prefix * np.flip(suffix) % M, (n, m)).tolist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        pre = [[1] * (m + 1) for _ in range(n)]\n",
    "        suf = [[1] * (m + 1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                pre[i][j] = pre[i][j - 1] * grid[i][j] % 12345\n",
    "            for j in range(m)[::-1]:\n",
    "                suf[i][j] = suf[i][j + 1] * grid[i][j] % 12345\n",
    "        PRE = [1] * (n + 1)\n",
    "        SUF = [1] * (n + 1)\n",
    "        for i in range(n):\n",
    "            PRE[i] = PRE[i - 1] * pre[i][m - 1] % 12345\n",
    "        for i in range(n)[::-1]:\n",
    "            SUF[i] = SUF[i + 1] * pre[i][m - 1] % 12345\n",
    "        ans = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            x = PRE[i - 1] * SUF[i + 1]\n",
    "            for j in range(m):\n",
    "                y = pre[i][j - 1] * suf[i][j + 1]\n",
    "                ans[i][j] = x * y % 12345\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        mod = 12345\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        p = [[1] * m for _ in range(n)]\n",
    "        gpre = [1] * n\n",
    "        gsuf = [1] * n\n",
    "        rpre = [[1] * m for _ in range(n)]\n",
    "        rsuf = [[1] * m for _ in range(n)]\n",
    "        \n",
    "        for i in range(n):\n",
    "            now = 1\n",
    "            for j in range(m):\n",
    "                now = now * grid[i][j] % mod\n",
    "                rpre[i][j] = now\n",
    "            \n",
    "            now = 1\n",
    "            for j in range(m - 1, -1, -1):\n",
    "                now = now * grid[i][j] % mod\n",
    "                rsuf[i][j] = now\n",
    "        \n",
    "        now = 1\n",
    "        for i in range(n):\n",
    "            now = now * rpre[i][-1] % mod\n",
    "            gpre[i] = now\n",
    "            \n",
    "        now = 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            now = now * rpre[i][-1] % mod\n",
    "            gsuf[i] = now\n",
    "            \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                p[i][j] = 1\n",
    "                if i > 0:\n",
    "                    p[i][j] = p[i][j] * gpre[i - 1] % mod\n",
    "                if i + 1 < n:\n",
    "                    p[i][j] = p[i][j] * gsuf[i + 1] % mod\n",
    "                if j > 0:\n",
    "                    p[i][j] = p[i][j] * rpre[i][j - 1] % mod\n",
    "                if j + 1 < m:\n",
    "                    p[i][j] = p[i][j] * rsuf[i][j + 1] % mod\n",
    "            \n",
    "        return p\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        def func(grid):\n",
    "            import numpy as np\n",
    "            grid = np.array(grid)\n",
    "            h,w = grid.shape\n",
    "\n",
    "            grid_flatten = grid.reshape(h*w)\n",
    "            p = np.zeros_like(grid_flatten)\n",
    "\n",
    "            grid_flatten = grid_flatten%12345\n",
    "\n",
    "            pre_list = []\n",
    "            suf_list = []\n",
    "            # 正向\n",
    "            total = 1\n",
    "            for i in range(h*w):\n",
    "                if grid_flatten[i]==0:\n",
    "                    total = 0\n",
    "                total = total*grid_flatten[i] % 12345\n",
    "                pre_list.append(total)\n",
    "\n",
    "            total = 1\n",
    "            for i in range(h*w-1,-1,-1):\n",
    "                if grid_flatten[i]==0:\n",
    "                    total =0\n",
    "                total = total*grid_flatten[i] % 12345\n",
    "                suf_list.insert(0,total)\n",
    "\n",
    "            p[0] = suf_list[1]\n",
    "            p[-1] = pre_list[-2]\n",
    "            for i in range(1,h*w-1):\n",
    "                p[i] = pre_list[i-1]*suf_list[i+1] % 12345\n",
    "\n",
    "            return p.reshape(h,w).tolist()\n",
    "        \n",
    "        return func(grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        MOD = 12345\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pre_row = [1] * (m+2)\n",
    "        suff_row = [1] * (m+2)\n",
    "        total_mod = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                total_mod = (total_mod*grid[i][j]) % MOD\n",
    "            pre_row[i+1] = total_mod\n",
    "            \n",
    "        total_mod = 1\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n):\n",
    "                total_mod = (total_mod*grid[i][j]) % MOD\n",
    "            suff_row[i+1] = total_mod\n",
    "            \n",
    "        pre_col = [[1] * (n+2) for _ in range(m)]\n",
    "        suff_col = [[1] * (n+2) for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            total_mod = 1\n",
    "            for j in range(n):\n",
    "                total_mod = (total_mod*grid[i][j]) % MOD\n",
    "                pre_col[i][j+1] = total_mod\n",
    "        for i in range(m):\n",
    "            total_mod = 1\n",
    "            for j in range(n-1, -1, -1):\n",
    "                total_mod = (total_mod*grid[i][j]) % MOD\n",
    "                suff_col[i][j+1] = total_mod       \n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = (pre_row[i] * suff_row[i+2] * pre_col[i][j] * suff_col[i][j+2])%MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "def pow_mod(a, b, MOD):\n",
    "    res = 1\n",
    "    while b:\n",
    "        if b & 0x1:\n",
    "            res = (res * a) % MOD\n",
    "        a = (a * a) % MOD\n",
    "        b = b >> 1\n",
    "    return res\n",
    "\n",
    "\n",
    "def extended_gcd(a, b):\n",
    "    if b == 0:\n",
    "        return a, 1, 0\n",
    "    else:\n",
    "        d, x1, y1 = extended_gcd(b, a % b)\n",
    "        x = y1\n",
    "        y = x1 - (a // b) * y1\n",
    "        return d, x, y\n",
    "\n",
    "\n",
    "# 相比费马小定理，这里不要求MOD是质数，只需要确保b和MOD是互质就行\n",
    "# b * x + MOD * y =  1(% MOD)\n",
    "def mod_inverse(b, MOD):\n",
    "    d, x, y = extended_gcd(b, MOD)\n",
    "    assert (d == 1)\n",
    "    return x % MOD\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        # 12345 = 3,5,823\n",
    "        MOD = 12345\n",
    "        A, B, C, D = 0, 0, 0, 1\n",
    "        encode = {}\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                a, b, c = 0, 0, 0\n",
    "                x = grid[i][j]\n",
    "                while x % 3 == 0:\n",
    "                    a += 1\n",
    "                    x = x // 3\n",
    "                while x % 5 == 0:\n",
    "                    b += 1\n",
    "                    x = x // 5\n",
    "                while x % 823 == 0:\n",
    "                    c += 1\n",
    "                    x = x // 823\n",
    "                encode[(i, j)] = (a, b, c, x)\n",
    "                A, B, C = A + a, B + b, C + c\n",
    "                D = (D * x) % MOD\n",
    "\n",
    "        # print(A, B, C, D)\n",
    "        ans = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                a, b, c, d = encode[(i, j)]\n",
    "                # (D/d) % MOD\n",
    "                # D % MOD * (d^(-1) % MOD)\n",
    "                v = D * mod_inverse(d, MOD)\n",
    "                v = (v * pow_mod(3, (A - a), MOD)) % MOD\n",
    "                v = (v * pow_mod(5, (B - b), MOD)) % MOD\n",
    "                v = (v * pow_mod(823, (C - c), MOD)) % MOD\n",
    "                ans[i][j] = v\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 12345\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        c = Counter()\n",
    "        mm = {}\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        Tot = 1\n",
    "        pos = {}\n",
    "        arr = []\n",
    "        for i, ll in enumerate(grid):\n",
    "            for j, v in enumerate(ll):\n",
    "                Tot *= v\n",
    "                Tot %= MOD\n",
    "                pos[v] = i*n + j\n",
    "                arr.append(v)\n",
    "\n",
    "        N = m*n\n",
    "        vals = [0] * (4 * N + 100)\n",
    "\n",
    "        def push_up(x):\n",
    "            vals[x] = vals[x << 1] * vals[(x<<1) + 1]\n",
    "            vals[x] %= MOD\n",
    "\n",
    "        def build(x, l, r):\n",
    "            if l == r:\n",
    "                vals[x] = arr[l] % MOD\n",
    "                return\n",
    "\n",
    "            mid = (l + r) >> 1\n",
    "            build(x<<1, l, mid)\n",
    "            build((x<<1) | 1, mid+1, r)\n",
    "            push_up(x)\n",
    "\n",
    "        def query(x, l, r, ql, qr):\n",
    "            if l == ql and r == qr:\n",
    "                return vals[x]\n",
    "\n",
    "            mid = (l + r) >> 1\n",
    "            if qr <= mid:\n",
    "                return query(x<<1, l, mid, ql, qr)\n",
    "            elif ql >= mid+1:\n",
    "                return query((x<<1)|1, mid+1, r, ql, qr)\n",
    "            else:\n",
    "                val1 = query(x<<1, l, mid, ql, mid)\n",
    "                val2 = query((x<<1)|1, mid+1, r, mid+1, qr)\n",
    "                return (val1 * val2) % MOD\n",
    "\n",
    "        build(1, 0, N-1)\n",
    "\n",
    "\n",
    "        cc = {}\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ret = [[0] * n for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "\n",
    "                # if grid[i][j] in cc:\n",
    "                #     ret[i][j] = cc[grid[i][j]]\n",
    "                #     continue\n",
    "\n",
    "                idx = pos[grid[i][j]]\n",
    "                ans = 1\n",
    "                if idx-1 >= 0:\n",
    "                    ans *= query(1, 0, N-1, 0, idx-1)\n",
    "                    ans %= MOD\n",
    "\n",
    "                if idx+1 <= N-1:\n",
    "                    ans *= query(1, 0, N-1, idx+1, N-1)\n",
    "                    ans %= MOD\n",
    "\n",
    "                ret[i][j] = ans\n",
    "                cc[grid[i][j]] = ans\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_prime_factors(n):\n",
    "    ans = []\n",
    "    i = 2\n",
    "    while i <= sqrt(n):\n",
    "        while n % i == 0:\n",
    "            ans.append(i)\n",
    "            n //= i\n",
    "        i += 1\n",
    "    if n > 1:\n",
    "        ans.append(n)\n",
    "    return ans\n",
    "\n",
    "def exgcd(a, b):\n",
    "    if b == 0:\n",
    "        x = 1\n",
    "        y = 0\n",
    "        return x, y\n",
    "    x1, y1 = exgcd(b, a % b)\n",
    "    x = y1\n",
    "    y = x1 - (a // b) * y1\n",
    "    return x, y\n",
    "\n",
    "# If gcd(a, mod) = 1, return x such that a * x % mod = 1.\n",
    "def inv(a, mod):\n",
    "    x, y = exgcd(a, mod)\n",
    "    return ((x % mod) + mod) % mod\n",
    "\n",
    "# Chinese Remainder Theory\n",
    "# k = len(mod) = len(r)\n",
    "# x % mod[i] = r[i], 0 <= i < k\n",
    "# Return x % (mod[0] * mod[1] * ... * mod[k-1])\n",
    "# CRT([3,5,7],[2,3,2]) = 23\n",
    "def CRT(mod, r):\n",
    "    k = len(r)\n",
    "    n = 1\n",
    "    ans = 0\n",
    "    for i in range(k):\n",
    "        n = n * mod[i]\n",
    "    for i in range(k):\n",
    "        m = n // mod[i]\n",
    "        b = inv(m, mod[i])\n",
    "        ans = (ans + r[i] * m * b % n) % n\n",
    "    return (ans % n + n) % n\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def calc(mod):\n",
    "            ans = [[0 for j in range(n)] for i in range(m)]\n",
    "            cnt = sum(int(grid[i][j] % mod == 0) for j in range(n) for i in range(m))\n",
    "            if cnt >= 2:\n",
    "                return ans\n",
    "            prod = 1\n",
    "            target = -1\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] % mod == 0: \n",
    "                        target = (i, j)\n",
    "                        continue\n",
    "                    prod *= grid[i][j]\n",
    "                    prod %= mod\n",
    "            if cnt == 1:\n",
    "                i, j = target    \n",
    "                ans[i][j] = prod\n",
    "                return ans\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    ans[i][j] = prod * inv(grid[i][j], mod) % mod\n",
    "            return ans\n",
    "\n",
    "        mod = 12345 \n",
    "        primes = get_prime_factors(mod)\n",
    "\n",
    "        r = [[[] for j in range(n)] for i in range(m)]\n",
    "        for p in primes:\n",
    "            ret = calc(p)\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    r[i][j].append(ret[i][j])\n",
    "\n",
    "        return [[CRT(primes, r[i][j]) for j in range(n)] for i in range(m)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        prime1 = 3\n",
    "        prime2 = 5\n",
    "        prime3 = 823\n",
    "        pow1 = prime1 - 2\n",
    "        pow2 = prime2 - 2\n",
    "        pow3 = prime3 - 2\n",
    "        divisor = 12345\n",
    "        multi1 = prime2 * prime3 * pow(prime2 * prime3, pow1, prime1)\n",
    "        multi2 = prime1 * prime3 * pow(prime1 * prime3, pow2, prime2)\n",
    "        multi3 = prime2 * prime1 * pow(prime2 * prime1, pow3, prime3)\n",
    "        print(multi1)\n",
    "        print(multi2)\n",
    "        print(multi3)\n",
    "        mod1 = 1\n",
    "        mod2 = 1\n",
    "        mod3 = 1\n",
    "        aa1 = aa2 = aa3 = None\n",
    "        for i, line in enumerate(grid):\n",
    "            for j, num in enumerate(line):\n",
    "                if aa1 is None and num % prime1 == 0:\n",
    "                    aa1 = (i, j)\n",
    "                mod1 = mod1 * num % prime1\n",
    "                if aa2 is None and num % prime2 == 0:\n",
    "                    aa2 = (i, j)\n",
    "                mod2 = mod2 * num % prime2\n",
    "                if aa3 is None and num % prime3 == 0:\n",
    "                    aa3 = (i, j)\n",
    "                mod3 = mod3 * num % prime3\n",
    "        ans1 = []\n",
    "        ans2 = []\n",
    "        ans3 = []\n",
    "        for line in grid:\n",
    "            tmp1 = []\n",
    "            tmp2 = []\n",
    "            tmp3 = []\n",
    "            for num in line:\n",
    "                tmp1.append(mod1 * pow(num, pow1, prime1) % prime1)\n",
    "                tmp2.append(mod2 * pow(num, pow2, prime2) % prime2)\n",
    "                tmp3.append(mod3 * pow(num, pow3, prime3) % prime3)\n",
    "            ans1.append(tmp1)\n",
    "            ans2.append(tmp2)\n",
    "            ans3.append(tmp3)\n",
    "        if aa1:\n",
    "            x, y = aa1\n",
    "            mod = 1\n",
    "            for i, line in enumerate(grid):\n",
    "                for j, num in enumerate(line):\n",
    "                    if i == x and j == y:\n",
    "                        continue\n",
    "                    mod = mod * num % prime1\n",
    "            ans1[x][y] = mod\n",
    "        if aa2:\n",
    "            x, y = aa2\n",
    "            mod = 1\n",
    "            for i, line in enumerate(grid):\n",
    "                for j, num in enumerate(line):\n",
    "                    if i == x and j == y:\n",
    "                        continue\n",
    "                    mod = mod * num % prime2\n",
    "            ans2[x][y] = mod\n",
    "        if aa3:\n",
    "            x, y = aa3\n",
    "            mod = 1\n",
    "            for i, line in enumerate(grid):\n",
    "                for j, num in enumerate(line):\n",
    "                    if i == x and j == y:\n",
    "                        continue\n",
    "                    mod = mod * num % prime3\n",
    "            ans3[x][y] = mod\n",
    "        ans = []\n",
    "        for line1, line2, line3 in zip(ans1, ans2, ans3):\n",
    "            tmp = []\n",
    "            for num1, num2, num3 in zip(line1, line2, line3):\n",
    "                tmp.append((num1 * multi1 + num2 * multi2 + num3 * multi3) % divisor)\n",
    "            ans.append(tmp)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
